package com.example;

/**
 * @Author loubobooo
 * @Description #101. 对称二叉树
 * @Date 2020/3/24
 */
public class SymmetricTree {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    /**
     * @Author loubobooo
     * @Description 给定一个二叉树，检查它是否是镜像对称的。
     *
     * 例如，二叉树[1,2,2,3,4,4,3] 是对称的。
     *
     *     1
     *    / \
     *   2   2
     *  / \ / \
     * 3  4 4  3
     * 但是下面这个[1,2,2,null,3,null,3] 则不是镜像对称的:
     *
     *     1
     *    / \
     *   2   2
     *    \   \
     *    3    3
     * @Date 2020/3/24 10:37
     * @Param
     * @return
     **/
    public boolean isSymmetric(TreeNode root) {
        // 解决空指针的问题
        if(root == null){
            return true;
        }
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode t1, TreeNode t2){
        // 终止条件
        // 1. 左右子树都为空
        if (t1 == null && t2 == null) {
            return true;
        }
        // 2. 只有一个为空
        if (t1 == null || t2 == null) {
            return false;
        }
        // 判断两个指针当前值是否相等
        if(t1.val != t2.val){
            return false;
        }
        // 递归过程：
        // 判断A的右子树和B的左子树是否对称
        // 判断A的左子树和B的右子树是否对称
        return isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right);
    }


}
